This application claims priority to Japanese Patent Application No. P2000-274986.
1. Field of the Invention
The present invention relates to a method of improving the delay characteristics of existing logic circuits, thereby providing logic circuits operating at a faster speed, and a method of synthesizing high-speed logic circuits by using a Hardware Description Language (HDL) such as Verilog or VHDL.
2. Description of the Background
Many study results about methods for making logic circuits operate at faster speeds by modifying existing logic circuits have been published.
The maximum operating speed of a circuit depends upon the delay of a path called a critical path for which the longest delay is observed when a signal from the input terminal of the circuit is carried across the path to the output terminal. Thus, it is important to reduce the critical path delay. For example, in IEEE Transactions on Computer-Aided Design, Vol. CAD-6, No. 6, pp. 106201981 (1987) (xe2x80x9creference 1xe2x80x9d), a method for increasing the speed of a circuit is described which applies the following two methods to all gates constituting a critical path:
(1) The first method optimizes the gate drive capability (inserting a buffer as required), whereby the delay per gate is reduced for all gates along the critical path.
(2) The second method applies circuit restructuring based on Boolean equations to each circuit comprising a plurality of gates along the path, thereby reforming the entire circuit into one with shorter depth of the critical path, that is, the path comprises a decreased number of stages. In this way, the number of stages, or the depth of the critical path, can be reduced, and the path delay will decrease.
By applying the above two methods repeatedly, a logic circuit operating at a faster speed may be obtained.
In Japanese Patent Laid-Open Publication No. Hei 11-161470 (xe2x80x9creference 2xe2x80x9d), a method for increasing the speed of a logic circuit utilizing a path depth reduction method based on selectors was introduced. In this method, AND gates and OR gates that constitute a logic circuit are translated into logically equivalent selectors with two inputs and one output. Thus, the logic circuit is transformed into one comprising the selectors with two inputs and one output. Then, a critical path is detected in the resulting selector-based circuit. The detected critical path is separated into sections of two selector stages, and the path depth is reduced by applying a path depth reduction pattern that transforms the two stages into a one stage path section. Finally, all selectors are converted into pass transistor selectors with two inputs and one output, each of which comprises a pass-transistor circuit. In this way, a high-speed pass-transistor circuit with the same logical function as the original logic circuit is obtained.
The reference describes a path depth reduction method based on selectors by which two stages in path sections can be reduced to one stage in any kind of circuit. Thus, path depth reduction is possible for a circuit for which it is impossible to apply such circuit transformation based on Boolean equations as described in reference 1, and a resulting increase in circuit speed may be expected. In reference 2, in fact, an example case was introduced where a logic circuit operating three times as fast as the original circuit was successfully created.
Furthermore, in Proceeding of IEEE 1998 Custom Integrated Circuits Conference, pp. 291-294, (xe2x80x9creference 3xe2x80x9d), another method was introduced. In this method, after a logic circuit is replaced by the corresponding circuit comprising selectors with two inputs and one output and path depth reduction processing based on selectors is performed as in the method of reference 2, the selectors with two inputs and one output are mapped to a CMOS logic circuit consisting of AND/OR gates by an existing logic circuit synthesis tool.
According to reference 3, the depth reduction processing based on selectors is so powerful that a sufficient increase in circuit speed can be expected even if the selectors are eventually mapped again onto the CMOS logic circuit. In fact, an exemplary case was introduced where the method of reference 3 enabled the circuit to operate at double the speed of the circuit generated by the logic circuit synthesis tool alone. This method may be widely used because the mapping to a CMOS logic circuit is of general application in electronics.
The path depth reduction method based on selectors introduced in references 2 and 3 may improve performance in many cases. However, in a practical logic circuit, a plurality of paths may exist between an input terminal and an output terminal which are the starting point and the ending point of the paths. In other words, when a path from the input terminal is traced toward the output terminal, a path may be found that diverges at a gate and separates into two or more paths, and these paths may converge at another gate near the output terminal and rejoin one path to the output terminal (this path divergence and convergence will be referred to as xe2x80x9cpath loopingxe2x80x9d).
A path looping example is given in FIG. 3. Here, a path from IN1 to O1 diverges at the output N100 from S100 and separates into two paths (N100xe2x86x92I0 of S101 and I1 of S101), and these paths converge at S101 and rejoin one path. This path then diverges at the output N101 from S101 and separates into two paths (N101xe2x86x92I0 of S102 and I1 of S102), and these paths converge at S102 and rejoin one path.
If a critical path has such path looping and separates into a plurality of sub-paths, it is necessary to apply path depth reduction to these two or more sub-paths simultaneously to reduce the path delay. However, the path depth reduction method introduced in references 2 and 3 is effective only for a single path.
Basic path depth reduction patterns described in these references are shown as items b to e in FIG. 1. All of these patterns, in fact, can be used only for a single critical path. If we try to apply the path depth reduction pattern of item b in FIG. 1 to the two path stages formed by the two selectors S101 and S102 in the section from N100 to O1 of the circuit shown in FIG. 3, a circuit is translated as shown in FIG. 5 where the number of stages increased from three stages to four stages. As is evident from the above, the conventional method described in references 2 and 3 is not effective for a looping critical path.
In many cases, a circuit with a looping critical path may be found. A typical case is an arithmetic circuit such as an adder. For example, FIG. 19 shows a carry output C3 circuit portion extracted from a circuit comprising 4-bit ripple-carry adders. In this circuit, the critical path loops in three sections (G10xe2x86x92G11-G12/G16xe2x86x92G13, G13xe2x86x92G17-G18/G21xe2x86x92G22, and G22xe2x86x92G23-G24/G27xe2x86x92G28); An arithmetic circuit such as an adder is essential for an LSI that must execute arithmetic operation, for example, a CPU to execute arithmetic calculation and a DSP chip for signal processing installed in mobile telephone equipment. In terms of practical applications, thus, it is very important to provide a delay reduction method that is also effective for a looping critical path.
In the method of prior art reference 3, described above, the selectors with two inputs and one output, generated after the path depth reduction processing based on selectors, are mapped onto a general CMOS logic circuit consisting of AND/OR gates by a logic circuit synthesis tool. Without considering the delay of the circuit generated after these selectors with two inputs and one output are mapped to CMOS gates, the critical path in the circuit consisting of selectors is presumed, and its depth reduction is performed. In this process, there is a possibility of reducing the number of stages, or the depth of a path, that is not critical. In the prior art reference 3, however, no concrete description is made for how to precisely presume a critical path in the circuit generated after mapping.
It has been shown experimentally that the reference 3 algorithm may output a circuit comprising complex gates that simply substitute for the selectors with two inputs and one output. In the method of reference 3, after the path depth reduction processing based on selectors is performed for the circuit comprising selectors, the reduced selectors are mapped onto a CMOS logic circuit. This may result in a circuit where the number of stages is virtually equal for all paths in the circuit, and no one critical path stands out as the preferred path to be input to the mapping tool. If complex gates that simply substitute for the selectors with two inputs and one output are prepared in a library cell set, a circuit may be generated in which no one critical path stands out because the selectors have simply been translated into the corresponding complex gates. The mapping tool, therefore, does not execute Boolean equation level optimization during the optimization process. The mapping tool tends to output a circuit generated only by simple translation.
Meanwhile, in general CMOS logic circuits, complex gate cells with four or more inputs cause longer delay time. In many cases, higher speed circuits can be generated by circuit configurations excluding these complex cells. In the method of reference 3, however, such complex gate cells of longer delay time are frequently used due to the mapping described above. To achieve a more effective delay reduction, it is necessary to control the mapping program by any means and to make the program use cells other than the complex gates with four or more inputs, so that the program will generate a higher speed logic circuit.
The present invention preferably provides a method of reducing the number of stages, or the depth of a critical path, in a logic circuit that may include a looping critical path. This method preferably includes generating a pass-transistor or CMOS logic circuit that can operate at high speed.
The present invention preferably also provides a method of precisely presuming a critical path in a circuit generated after the mapping of the selectors reduced by the path depth reduction processing based on selectors to the corresponding CMOS logic gates. This method preferably provides high-speed CMOS logic circuits of shorter delay than conventional methods.
The present invention may also provide higher-speed CMOS logic circuits by controlling an existing logic circuit synthesis tool to make the tool avoid using complex gates with four or more inputs, with which a longer delay may occur, when mapping the selectors to the corresponding CMOS logic gates.
The present invention preferably enables the provision of high-speed CMOS logic circuits by using a selector-based delay model.
The present invention includes a logic circuit design method as a preferred embodiment in which a given logic circuit comprising gates is replaced by a corresponding one comprising selectors with two inputs and one output by translating the gates into logically equivalent functional selectors. Furthermore, by calculating the delay and slack of the obtained circuit made of selectors, a critical path is detected. A first node (N1) at which the detected critical path diverges and separates into two or more paths, a second node (N2) at which these paths converge, and a first local circuit (LC1) comprising a plurality of selectors with two inputs and one output (S0, S1, . . . S2) through which the critical path branches are routed from the first node (N1) to the second node (N2) are detected.
The number of stages, or the depth of the critical path, is preferably reduced by replacing the first local circuit (LC1) by a logically equivalent third selector (S3) with two inputs and one output. Where the control input S of the selector S3 is controlled by the first node (N1), the input I0 of the selector S3 is controlled by a second local circuit (LC2) that is formed by inputting a logical value of xe2x80x9c0xe2x80x9d to the first node (N1) in the first local circuit (LC1), and the input I1 of the selector S3 is controlled by a third local circuit (LC3) that is formed by inputting a logical value of xe2x80x9c1xe2x80x9d to the first node (N1) in the first local circuit (LC1). By executing the above path depth reduction processing once, or by repeating it two or more times, the number of stages (the depth) of the entire circuit may be reduced.
From the logic circuit comprising the selectors with two inputs and one output, obtained by the above path depth reduction processing, a CMOS logic circuit of improved delay is preferably generated by mapping these selectors to AND and OR CMOS logic gates. When this mapping is executed, the use of complex gates with four or more inputs is selectively inhibited. Consequently, the mapping generates a high-speed CMOS logic circuit of shorter delay time as the intended logic circuits of improved delay. It should be noted here that the term xe2x80x9ccomplex gatesxe2x80x9d or xe2x80x9ccomplex cellsxe2x80x9d are cells which combine a plurality of primitive functions (for example, AND or OR functions). These complex gates or complex cells are used instead of a combination of cells that each has a primitive function because a complex gate may have an advantage in seize or power consumption.
Moreover, in at least one preferred embodiment of the present invention, a library is provided for storing the descriptions of the logical functions of the selectors with two inputs and one output so that these selectors used for processing of the invention will be independent of the CMOS technology.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings and attached claims.